package leetcode.day;

import java.util.*;

// 118. 杨辉三角
public class Generate {

    public static void main(String[] args) {
        System.out.println(generate(5));
    }

    public static List<List<Integer>> generate(int numRows) {
        List<List<Integer>> ret = new ArrayList<>();
        for (int i = 0; i < numRows; i++) {
            List<Integer> row = new ArrayList<>();
            for (int j = 0; j <= i; j++) {
                if (j == 0 || j == i) {
                    row.add(1);
                } else {
                    row.add(ret.get(i - 1).get(j - 1) + ret.get(i - 1).get(j));
                }

            }
            ret.add(row);
        }
        return ret;
    }

    // 找规律-----发现当前一行只比上一行多了一个元素，最最关键的一点：本行元素等于上一行元素往后错一位再逐个相加：
    public static List<List<Integer>> generate2(int numRows) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> t = new ArrayList<>();
        t.add(1);
        res.add(t);
        List<Integer> a = new ArrayList<>();
        List<Integer> b = new ArrayList<>();
        // 第一行已经手写，从第二行开始即可
        for (int i = 1; i < numRows; i++) {
            // res.get(res.size()-1) 上一行
            t = new ArrayList<Integer>(res.get(res.size() - 1));
            t.add(0); // 末尾补0，用来相加
            a = new ArrayList<>(t);
            // 移除0
            t.remove(t.size() - 1);
            // 在首填0
            t.add(0, 0);
            b = new ArrayList<>(t);
            List<Integer> list = new ArrayList<>();
            for (int j = 0; j < a.size(); j++) {
                list.add(a.get(j) + b.get(j));
            }
            res.add(list);
        }
        return res;
    }

}
